package com.yangzhe.algorithm.c006;

// 峰值元素是指其值严格大于左右相邻值的元素
// 给你一个整数数组 nums，已知任何两个相邻的值都不相等
// 找到峰值元素并返回其索引
// 数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
// 你可以假设 nums[-1] = nums[n] = 无穷小
// 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
public class Code04_FindPeakElement {

    public static void main(String[] args) {

        Solution solution = new Solution();
        int[] arr = new int[] {1, 2, 1};
        solution.findPeakElement(arr);

    }
    // 测试链接 : https://leetcode.cn/problems/find-peak-element/
    static class Solution {


        public int findPeakElement(int[] nums) {
            // 由于两边都是 负无穷，所以0位置就是峰值
            if (nums.length == 1) {
                return 0;
            }

            // 左侧负无穷，比右侧大，0位置就是峰值
            if (nums[0] > nums[1]) {
                return 0;
            }

            int n = nums.length;
            // 右侧负无穷，比左侧大，n -1 位置就是峰值
            if (nums[n - 1] > nums[n - 2]) {
                return n - 1;
            }

            // 0-1是上升，n-1 n-2是下降，中间必有峰值
            // 如果m-1 m是下降，则1到m-1中间必有峰值
            // 如果m m + 1是上升，则m+1到n-2中间必有峰值
            // 所以可以用二分法搜索峰值
            int l = 1;
            int r = n - 2;
            int m = 0;
            while (l <= r) {
                m = l + ((r - l) >> 1);
                if (nums[m - 1] > nums[m]) {
                    r = m - 1;
                } else if (nums[m + 1] > nums[m]) {
                    l = m + 1;
                } else {
                    return m;
                }
            }
            return -1;
        }
    }

}
